---

BrushOctree.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file BrushOctree.hpp
///
/// @brief Brush Octree header
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Nov 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks January Release
///
/// @date Dec 2002
/// @author Assassin
/// @remarks Rewrite for new scenegraph code
///
///////////////////////////////////////////////////////////////////////////////

#ifndef BRUSH_OCTREE_HPP
#define BRUSH_OCTREE_HPP

#include "deGlobalTypes.hpp"
#include "deList.hpp"
#include "deArray.hpp"
#include "deBrush_priv.hpp"

#include "deHash.hpp"
#include "deFunctors.hpp"

class deBrushOctree
{
public:
    class deIndexedPoly
    {
    public:
        //deBoolean CanRemove;
        s32         NumVerts;
        long        PolyIndex;
        long        TextureIndex;
        u16 *       PosIndices;
        u16 *       NormIndices;
        u16 *       MatIndices;
        deDouble    Dist;
        deVec3d     Normal;
        ~deIndexedPoly()
        { delete[] PosIndices; }
        deIndexedPoly(s32 vertnum = 3)
        {
            //CanRemove = deFALSE;
            NumVerts = vertnum;
            PosIndices = new u16[NumVerts*3];
            NormIndices= &PosIndices[NumVerts];
            MatIndices = &PosIndices[NumVerts*2];
            TextureIndex = -1;
            PolyIndex = -1;
        }
        deIndexedPoly(const deIndexedPoly & ref) 
        {   
            //CanRemove = deFALSE;
            Normal = ref.Normal;
            Dist = ref.Dist;
            NumVerts = ref.NumVerts;
            TextureIndex = ref.TextureIndex;
            PosIndices = new u16[NumVerts*3];
            NormIndices= &PosIndices[NumVerts];
            MatIndices = &PosIndices[NumVerts*2];
            memcpy(PosIndices, ref.PosIndices, NumVerts*sizeof(u16)*3);
            PolyIndex = -1;
        }
        deIndexedPoly & operator=(const deIndexedPoly & ref)
        {   
            Normal = ref.Normal;
            Dist = ref.Dist;
            TextureIndex = ref.TextureIndex;
            NumVerts = ref.NumVerts;
            if (NumVerts != ref.NumVerts)
            {
                delete[] PosIndices;
                PosIndices = new u16[NumVerts*3];
                NormIndices= &PosIndices[NumVerts];
                MatIndices = &PosIndices[NumVerts*2];
            }
            memcpy(PosIndices, ref.PosIndices, NumVerts*sizeof(u16)*3);
            PolyIndex = -1;
            return *this;
        }
        void Resize(s32 vertnum)
        {   
            if (vertnum == NumVerts) return;
            u16* pTemp;
            NumVerts = vertnum;

            pTemp = new u16[NumVerts*3];
            memcpy(pTemp, PosIndices, NumVerts*sizeof(u16)*3);
            delete[] PosIndices;
            PosIndices = pTemp;
            NormIndices= &PosIndices[NumVerts];
            MatIndices = &PosIndices[NumVerts*2];
        }
    };

    struct deVertMat
    {
        deARGB Diffuse;
        deTexCoord UV;
    };

private:
    struct OctNode
    {
        long Depth;
        DWORD Contents;
        deVec3d Min, Max;
        struct OctNode* Children[9];
        deTArray <long> PolyIndexList;
    };

public:
    deBrushOctree();
    ~deBrushOctree();

    deBoolean AddPositions(deVec3d *VertArray, u16 NumVerts, u16 &Offset);
    deBoolean AddNormals(deVec3d *VertArray, u16 NumVerts, u16 &Offset);
    deBoolean AddVertMats(deVertMat *VertArray, u16 NumVerts, u16 &Offset);
    deBoolean AddPolyGetRef(deIndexedPoly* & poly);
    deBoolean AddPoly(deIndexedPoly * poly, u16 PosOffset, u16 NormOffset, u16 MatOffset);

    deBoolean GetPoly(deIndexedPoly* & poly, long PolyIndex);

    deBoolean RemovePoly(const deIndexedPoly * poly);

    deBoolean Generate();
    deBoolean Clear();

    deBoolean GetPolysInBox(const deVec3d & Min, const deVec3d & Max, deTArray <deIndexedPoly*> &PolyArray, OctNode * node = NULL);
    deBoolean GetAllPolys(deTArray <deIndexedPoly*>* &PolyArray);
    deBoolean GetPolyInfo(deIndexedPoly* poly, deVec3d* &PosArray, deVec3d* &NormArray, deVertMat* &VertMatArray);
/*  deBoolean RayTrace(const deVec3d & start, const deVec3d & end, deIndexedPoly * & HitPoly, deVec3d & intersect);
    
    deBoolean AddMesh(deBrushOctree & adder);
    deBoolean SubtractMesh(deBrushOctree & cutter);
    deBoolean IntersectMesh(deBrushOctree & brush);

    deBoolean Copy(deBrushOctree & target);
*/
private:
    OctNode *m_Root;
    deTList  <long>                 m_PolyAddList;  // list of polygons that haven't been put into the array yet
    deTList  <long>             m_PolyRemoveList;   // list of polygons that have been invalidated and can be replaced
    deTArray <deIndexedPoly*>       m_PolyArray;    // all the polygons that are inserted into the octree
    deTArray <deTArray<OctNode*> >  m_PolyNodes;    // lists of which nodes a polygon is "in"
    deTArray <deVec3d>              m_Positions;    // positions buffer
    deTArray <deVec3d>              m_Normals;      // normals buffer
    deTArray <deVertMat>            m_VertMats;     // materials buffer
    // for splitting polygons
    dePlane     m_SplittingPlane;
    deTHashFunctor<u16,HashEdge>    m_SplitPosHash;
    deTHashFunctor<u16,HashEdge>    m_SplitNormHash;
    deTHashFunctor<u16,HashEdge>    m_SplitMatHash;
    
//  void CopyNode(OctNode * source, OctNode * & target);
    void DestroyNode(OctNode * node);

    deBoolean   InsertPolyIntoTree(long PolyIndex);
    u8      DecideChildNodes(long PolyIndex, OctNode* Node);
    OctNode*    GetSmallestNodeForAABB(const deAABB & bbox);
    deBoolean   InsertPolyIntoNode(long PolyIndex, OctNode* Node);

/*
    void SubdivideNode(OctNode * node);
    void Optimize(OctNode * node);
    void InsertPoly(long index);
    bool InsertPoly(PolyPointer * p, OctNode * node);
    void RemovePoly(PolyPointer * p);
    bool PolyInNode(long poly, OctNode * node);
    long PolysIntersecting(deBPoly & tri, deTList <PolyPointer*> & polylist, bool CheckIntersection = false);
    long GetAllPolys(deTList <PolyPointer*> & polylist, OctNode * node);
    void Split(deBrushOctree & In1, deBrushOctree & In2, deBrushOctree & Out1, deBrushOctree & Out2);
*/

    static char      FrontmostOctNodeCorner(const deVec3d & norm);
    static void      OctNodeCorner(const OctNode* node, const char Corner, deVec3d & vec);
    static void      OctNodeMidPoint(const OctNode* node, const char MidPoint, deVec3d & vec);
    static deBoolean OctNodeIntersectsPlane(OctNode *node, const dePlane & plane);
    static inline void OctNodeCenter(const OctNode* node, deVec3d & vec)
    {
        vec = node->Min; vec += node->Max; vec *= 0.5;
    }

    // not static because they depend on the current octree's vertices
    // mostly polygon stuff
    char        TriLineIntersect(   const deIndexedPoly * T, u16 VertNum,
                                    const deVec3d & LinePt1, const deVec3d & LinePt2, 
                                    deVec3d & Res, deBoolean & HitEdge); // not implemented
    deBoolean   PolyPlaneIntersect(const deVec3d & norm, const deDouble & dist, const deIndexedPoly * poly, deVec3d* & ResPair);
    deBoolean   PolyPolyIntersect(const deIndexedPoly * p1, const deIndexedPoly * p2);
    deBoolean   MakePlane(long PolyIndex);
    deBoolean   MakePlane(deIndexedPoly * input);
    deBoolean   SplitPoly(const deIndexedPoly * input, deIndexedPoly* & out1, deIndexedPoly* & out2);
    u16         SplitEdgePos(const HashEdge & Edge, deDouble & Percent);
    u16         SplitEdgeNorm(const HashEdge & Edge, const deDouble & Percent);
    u16         SplitEdgeMat(const HashEdge & Edge, const deDouble & Percent);

    deBoolean   SplitAllPolys(deIndexedPoly* splitter);

    deBoolean   AssembleVertexBuffer(IdeVertexBuffer * pVB);
    deBoolean   AssembleVertexBufferNoNormals(IdeVertexBuffer * pVB);
    deBoolean   TriangulateIndices(const deIndexedPoly * Poly, u16 LastVertIndex, u16 * IndexArray3);

    void TEST();
};

/*
        ________Max
       / 6 / 7 /|
      /___/___/7|       Y+  Z+
     / 2 / 3 /| |       |  /
    /___/___/3|/|       | /
    |   |   | /5|       |/____X+
4=> | 2 | 3 |/| |
    |-------|1|/
    | 0 | 1 | /
    |___|___|/
  Min

  mins:
  X: i%2 == 0
  Y: i%4 <  2
  Z: i   <  4

*/

#endif

---